class Solution5 {
    public ListNode sortList(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        if(head==null||head.next==null){
            return head;
        }
        ListNode pre=null;
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        pre=head;
        ListNode cur=new ListNode(0);
        ListNode newHead=cur;
        while(pre!=null&&slow!=null){
            if(pre.val<slow.val){
                cur.next=pre;
                cur=cur.next;
            }else{
                cur.next=slow;
                cur=cur.next;
            }
            pre=pre.next;
            slow=slow.next;
        }
        if(pre!=null){
            cur.next=pre;
            cur=cur.next;
            pre=pre.next;
        }
        if(slow!=null){
            cur.next=slow;
            cur=cur.next;
            slow=slow.next;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        Solution5 solution5=new Solution5();
        ListNode head=new ListNode(4);
        ListNode cur1=new ListNode(2);
        ListNode cur2=new ListNode(3);
        ListNode cur3=new ListNode(1);
        head.next=cur1;
        cur1.next=cur2;
        cur2.next=cur3;

        solution5.sortList(head);
    }
}